#pragma once
#include <iostream>
#include <vector>
#include <list>

namespace mypriority_queue
{

    template <class T>
    struct less
    {
        bool operator()(const T &x, const T &y)
        {
            return x < y;
        }
    };

    template <class T>
    struct greater
    {
        bool operator()(const T &x, const T &y)
        {
            return x > y;
        }
    };

    template <class T, class Container = std::vector<T>, class Compare = less<T>>
    class priority_queue
    {
    private:
        Container _pque;

    public:
        void AdjustUp()
        {
            int child = _pque.size() - 1;
            int parent = (child - 1) / 2;
            Compare com;
            while (child > 0)
            {
                if (com(_pque[parent], _pque[child]))
                {
                    std::swap(_pque[parent], _pque[child]);
                }
                else
                {
                    break;
                }
                child = parent;
                parent = (child - 1) / 2;
            }
        }

        void AdjustDown()
        {
            int parent = 0;
            int child = parent * 2 + 1;
            Compare com;
            while (child < _pque.size())
            {
                if (child + 1 < _pque.size() && com(_pque[child], _pque[child + 1]))
                {
                    child++;
                }
                if (com(_pque[parent], _pque[child]))
                {
                    std::swap(_pque[parent], _pque[child]);
                }
                else
                {
                    break;
                }
                parent = child;
                child = parent * 2 + 1;
            }
        }
        void push(const T &val)
        {
            _pque.push_back(val);
            AdjustUp();
        }
        void pop()
        {
            std::swap(_pque[0], _pque[_pque.size() - 1]);
            _pque.pop_back();
            AdjustDown();
        }
        const T &top()
        {
            return _pque.front();
        }
        bool empty()
        {
            return _pque.empty();
        }
        size_t size()
        {
            return _pque.size();
        }
        void swap(priority_queue &val)
        {
            _pque.swap(val._pque);
        }
    };
}
